package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-28 12:39
 **/
public class LeetCode5938 {

    List<Integer> list = new ArrayList<>();

    public List<Integer> targetIndices(int[] nums, int target) {
        Arrays.sort(nums);
        binarySearch(nums, 0, nums.length - 1, target);
        return list;
    }

    void binarySearch(int[] nums, int low, int high, int target) {

        while (low <= high) {
            int avg = low + high >> 1;
            if (nums[avg] == target) {
                list.add(avg);
                int index = avg - 1;
                while (index >= 0 && nums[index] == target) {
                    list.add(0, index);
                    index--;
                }
                index = avg + 1;
                while (index < nums.length && nums[index] == target) {
                    list.add(index);
                    index++;
                }
                break;
            } else if (nums[avg] > target) {
                high = avg - 1;
            } else {
                low = avg + 1;
            }
        }
    }

}
